Search Results

Documents authored by Creignou, Nadia

Document
DOI: 10.4230/LIPIcs.MFCS.2022.38
Enumeration Classes Defined by Circuits

Authors: Nadia Creignou, Arnaud Durand, and Heribert Vollmer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration problems, e.g., from graph theory, Gray code enumeration, and propositional satisfiability in our classes. In this way we obtain a framework to distinguish between the complexity of different problems known to be in DelayP, for which a formal way of comparison was not possible to this day.
Cite as

Nadia Creignou, Arnaud Durand, and Heribert Vollmer. Enumeration Classes Defined by Circuits. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:LIPIcs.MFCS.2022.38,
  author =	{Creignou, Nadia and Durand, Arnaud and Vollmer, Heribert},
  title =	{{Enumeration Classes Defined by Circuits}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.38},
  URN =		{urn:nbn:de:0030-drops-168364},
  doi =		{10.4230/LIPIcs.MFCS.2022.38},
  annote =	{Keywords: Computational complexity, enumeration problem, Boolean circuit}
}
Document
DOI: 10.4230/DagRep.6.9.74
SAT and Interactions (Dagstuhl Seminar 16381)

Authors: Olaf Beyersdorff, Nadia Creignou, Uwe Egly, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 16381 "SAT and Interactions". The seminar brought together researchers from different areas from theoretical computer science involved with various aspects of satisfiability. A key objective of the seminar has been to initiate or consolidate discussions among the different groups for a fresh attack on one of the most important problems in theoretical computer science and mathematics.
Cite as

Olaf Beyersdorff, Nadia Creignou, Uwe Egly, and Heribert Vollmer. SAT and Interactions (Dagstuhl Seminar 16381). In Dagstuhl Reports, Volume 6, Issue 9, pp. 74-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{beyersdorff_et_al:DagRep.6.9.74,
  author =	{Beyersdorff, Olaf and Creignou, Nadia and Egly, Uwe and Vollmer, Heribert},
  title =	{{SAT and Interactions (Dagstuhl Seminar 16381)}},
  pages =	{74--93},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{9},
  editor =	{Beyersdorff, Olaf and Creignou, Nadia and Egly, Uwe and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.9.74},
  URN =		{urn:nbn:de:0030-drops-69116},
  doi =		{10.4230/DagRep.6.9.74},
  annote =	{Keywords: Combinatorics, Computational Complexity, P vs. NP, Proof Complexity, Quantified Boolean formulas, SAT-solvers, satisfiability problem}
}
Document
DOI: 10.4230/DagRep.2.11.87
SAT Interactions (Dagstuhl Seminar 12471)

Authors: Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)

Abstract
This report documents the programme and outcomes of Dagstuhl Seminar 12471 "SAT Interactions". The seminar brought together researchers from different areas from theoretical computer science as well as the area of SAT solvers. A key objective of the seminar has been to initiate or consolidate discussions among the different groups for a fresh attack on one of the most important problems in theoretical computer science and mathematics.
Cite as

Nadia Creignou, Nicola Galesi, Oliver Kullmann, and Heribert Vollmer. SAT Interactions (Dagstuhl Seminar 12471). In Dagstuhl Reports, Volume 2, Issue 11, pp. 87-101, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{creignou_et_al:DagRep.2.11.87,
  author =	{Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert},
  title =	{{SAT Interactions (Dagstuhl Seminar 12471)}},
  pages =	{87--101},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Creignou, Nadia and Galesi, Nicola and Kullmann, Oliver and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.11.87},
  URN =		{urn:nbn:de:0030-drops-39786},
  doi =		{10.4230/DagRep.2.11.87},
  annote =	{Keywords: satisfiability problem, computational complexity, P-NP question, proof complexity, combinatorics, SAT-solvers, quantified Boolean formulas}
}
Document
DOI: 10.4230/DagSemProc.10061.6
The Complexity of Reasoning for Fragments of Autoepistemic Logic

Authors: Nadia Creignou, Arne Meier, Michael Thomas, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)

Abstract
Autoepistemic logic extends propositional logic by the modal operator L. A formula that is preceded by an L is said to be "believed". The logic was introduced by Moore 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for autoepistemic logic.
Cite as

Nadia Creignou, Arne Meier, Michael Thomas, and Heribert Vollmer. The Complexity of Reasoning for Fragments of Autoepistemic Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:DagSemProc.10061.6,
  author =	{Creignou, Nadia and Meier, Arne and Thomas, Michael and Vollmer, Heribert},
  title =	{{The Complexity of Reasoning for Fragments of Autoepistemic Logic}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.6},
  URN =		{urn:nbn:de:0030-drops-25234},
  doi =		{10.4230/DagSemProc.10061.6},
  annote =	{Keywords: Autoepistemic logic, computational complexity, nonmonotonic reasoning, Post's lattice}
}
Document
DOI: 10.4230/DagSemProc.06401.1
06401 Abstracts Collection – Complexity of Constraints

Authors: Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract
From 01.10.06 to 06.10.06, the Dagstuhl Seminar 06401 ``Complexity of Constraints'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer. 06401 Abstracts Collection – Complexity of Constraints. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:DagSemProc.06401.1,
  author =	{Creignou, Nadia and Kolaitis, Phokion and Vollmer, Heribert},
  title =	{{06401 Abstracts Collection – Complexity of Constraints}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.1},
  URN =		{urn:nbn:de:0030-drops-8067},
  doi =		{10.4230/DagSemProc.06401.1},
  annote =	{Keywords: Constraint satisfaction problems, computational complexity, universal algebra, mathematical logic, finite model theory}
}
Document
DOI: 10.4230/DagSemProc.06401.2
06401 Executive Summary – Complexity of Constraints

Authors: Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract
In this document we describe the original motivation and goals of the seminar as well as the sequence of talks given during the seminar.
Cite as

Nadia Creignou, Phokion Kolaitis, and Heribert Vollmer. 06401 Executive Summary – Complexity of Constraints. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:DagSemProc.06401.2,
  author =	{Creignou, Nadia and Kolaitis, Phokion and Vollmer, Heribert},
  title =	{{06401 Executive Summary – Complexity of Constraints}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.2},
  URN =		{urn:nbn:de:0030-drops-8001},
  doi =		{10.4230/DagSemProc.06401.2},
  annote =	{Keywords: Constraint satisfaction problems, complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact